package primary.primary0;

import java.util.Arrays;
import java.util.HashMap;

/**
 *
 */
public class S0036有效的数独 {


    /**
     * 遍历1次，每次看每一组的记录，空间换时间?
     * 好像相比遍历三次来说，也没什么区别
     */
    class Solution {
        public boolean isValidSudoku(char[][] board) {
            int[][] rows = new int[9][9];
            int[][] columns = new int[9][9];
            int[][][] subboxes = new int[3][3][9];
            for (int i = 0; i < 9; i++) {
                for (int j = 0; j < 9; j++) {
                    char c = board[i][j];
                    if (c != '.') {
                        int index = c - '0' - 1;
                        rows[i][index]++;
                        columns[j][index]++;
                        subboxes[i / 3][j / 3][index]++;
                        // 这里先判断在赋值也行，那么对应的记录只需要赋值true和false就行，boolean[][] rows这种
                        if (rows[i][index] > 1 || columns[j][index] > 1 || subboxes[i / 3][j / 3][index] > 1) {
                            return false;
                        }
                    }
                }
            }
            return true;
        }
    }







    /**
     * 5, 问题不大。
     * 因为只是9*9的矩阵, 所以直接遍历也无妨, 而且复杂度都是n, 多遍历几轮也无所谓
     * 使用char + int来把char转成int
     * char的计算中
     * mark: '2' - 48 = 2;record[board[j][i] - 48] = true;这种操作很骚
     * '.' - 48 = -2;
     */
    public boolean isValidSudoku(char[][] board) {
        boolean[] record = new boolean[10];
        for(int i = 0; i < 9; i++){
            Arrays.fill(record, false);
            for(int j = 0; j < 9; j++){
                if(board[i][j] - 48 < 0) continue;
                if(record[board[i][j] - 48]){
                    System.out.println("第一轮" + i + " " + j);
                    return false;
                }else
                    record[board[i][j] - 48] = true;
            }
        }
        for(int i = 0; i < 9; i++){
            Arrays.fill(record, false);
            for(int j = 0; j < 9; j++){
                if(board[j][i] - 48 < 0) continue;
                if(record[board[j][i] - 48]){
                    System.out.println("第二轮" + i + " " + j);
                    return false;
                }else
                    record[board[j][i] - 48] = true;
            }
        }
        for(int i = 0; i < 3; i++){
            for(int j = 0; j < 3; j++){
                Arrays.fill(record, false);
                for(int m = 3*i; m < 3*i + 3; m++){
                    for(int n = 3*j; n < 3*j + 3; n++){
                        if(board[m][n] - 48 < 0) continue;
                        if(record[board[m][n] - 48])
                            return false;
                        else
                            record[board[m][n] - 48] = true;
                    }
                }
            }
        }
        return true;
    }

    /**
     * 别人的, 直观的写法是遍历三遍, 每遍计算一种形式(横, 竖, 3*3方格)有没有重合的
     * 但是也可以反过来, 遍历一次, 遍历到每个点的时候查看它在三种方式里有没有产生重合。
     * 关键是这样怎么判断3*3方式, 可以参考一下这里的找box序号的方式
     * 建议直接改成visited列表的形式
     */
    public boolean isValidSudoku2(char[][] board) {
        // init data
        HashMap<Integer, Integer>[] rows = new HashMap[9];
        HashMap<Integer, Integer> [] columns = new HashMap[9];
        HashMap<Integer, Integer> [] boxes = new HashMap[9];
        for (int i = 0; i < 9; i++) {
            rows[i] = new HashMap<Integer, Integer>();
            columns[i] = new HashMap<Integer, Integer>();
            boxes[i] = new HashMap<Integer, Integer>();
        }

        // validate a board
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                char num = board[i][j];
                if (num != '.') {
                    int n = (int)num; // char变int就是这么简单。
                    int box_index = (i / 3 ) * 3 + j / 3; // 懂了, 用这种方式来判断所在box的序号

                    rows[i].put(n, rows[i].getOrDefault(n, 0) + 1);
                    columns[j].put(n, columns[j].getOrDefault(n, 0) + 1);
                    boxes[box_index].put(n, boxes[box_index].getOrDefault(n, 0) + 1);

                    if (rows[i].get(n) > 1 || columns[j].get(n) > 1 || boxes[box_index].get(n) > 1)
                        return false;
                }
            }
        }

        return true;
    }

    public static void main(String[] args) {
        System.out.println('3' - '1');
        // mark: 结果为2，char之间可以直接减
    }
}

